﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0036_ClimbStairs : IAlgorithm
    {
        // 爬楼梯

        // 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

        // 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

        // 注意：给定 n 是一个正整数。

        public void Test()
        {
            // 算法参数定义
            var n = 4;
            // 算法执行与打印
            Console.WriteLine(ClimbStairs1(n));
        }

        // 算法
        public int ClimbStairs(int n)
        {
            if (n <= 1)
                return n;
            int f = 1, s = 2, sum = 0;
            while (n-- > 2)
            {
                sum = f + s;
                f = s;
                s = sum;
            }
            return sum;
        }

        public static int ClimbStairs1(int n)
        {
            return Fibonacci(n, 1, 1);
        }
        public static int Fibonacci(int n, int a, int b)
        {
            if (n <= 1)
                return b;
            return Fibonacci(n - 1, b, a + b);
        }
    }
}
